The most common technique for correcting a mixture of burst errors and random errors in data is by interleaving the codewords of an error correcting code (ECC). The conventional interleaving approach is to encode bytes 0 of each successive codeword columnwise, then bytes 1 of each codeword, etc., until all bytes of all codewords in each of a series of successive rectangular blocks have been written; whereas all codewords in each particular block are decoded successively row by row. As a result of this interleaving, an m-burst error will be spread serially over m successive codewords instead of all or most of all of these m errors being in a single codeword. This interleaving hopefully will assure that the error correction capability of each individual codeword will not be exceeded.
Various interleaving techniques are described by Clark et al. in "Error-correction Coding for Digital Communications", published by Plenum Press, 1981.
A widely used ECC is a so-called Reed-Solomon (RS) code. RS codes are byte-correcting codes over the finite Galois field denoted as GF(q), where q is a power of a prime number. A common value for q is 2.sup.8. An [n,k] RS code is one where the length n of a codeword in bytes is .ltoreq.q-1; the number of information bytes is k; the number of redundant bytes r is n--k; and the minimum distance d of the code is (n-k)+1. An [n,k] RS code can correct s errors and t erasures if 2s+t.ltoreq.(n-k). "Erasures" are errors where the location is known. Since one error is thus roughly equivalent to two erasures, the power of a decoder can be enhanced without increasing redundancy by treating certain errors as erasures.
U.S. Pat. No. 4,559,625 is the only prior art known to applicants which describes a forecasting technique to treat errors as erasures and thereby attempts to enhance decoding power. This patented technique has the following characteristics:
(1) If the codewords have a length (n) of 128 bytes, which is common, this technique requires that 127 (n-1) codewords (an undesirably high number) must be interleaved to complete helical symmetry; otherwise, additional complexities will be introduced in the burst forecasting technique.
(2) Whenever a codeword has a correctable error, the locations in the next codeword adjacent to each such error are flagged, and errors are automatically forecasted as erasures at these adjacent locations.
(3) Codewords are encoded in staggered blocks; i.e., row by row but with corresponding bytes of successive codewords laterally offset from codeword to codeword.
These characteristics and their consequences will be discussed more fully in the following description.
There is a need for a technique for decoding ECC codewords that enhances the decoding power over that described in the prior art.